package main

type BinaryIndexedTree struct {
	tree     []int
	capacity int
}

func (bit *BinaryIndexedTree) Init(nums []int) {
	bit.tree, bit.capacity = make([]int, len(nums)+1), len(nums)+1
	for i := 1; i <= len(nums); i++ {
		for j := i - 1; j >= i-lowbit(i); j-- {
			bit.tree[i] += nums[j]
		}
	}
}

func (bit *BinaryIndexedTree) Add(index int, val int) {
	for index <= bit.capacity {
		bit.tree[index] += val
		index += lowbit(index)
	}
}

func (bit *BinaryIndexedTree) Query(index int) int {
	sum := 0

	for index >= 1 {
		sum += bit.tree[index]
		index -= lowbit(index)
	}

	return sum
}

func lowbit(idx int) int {
	return idx & (-idx)
}
